#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "data_struct.h"

/* 封装优先级队列(使用堆结构) */
/******************************/
static inline int LEFT_PQ(int index)	//节点下标为index左孩子的下标
{
	return (index << 1) + 1;
}
static inline int RIGHT_PQ(int index)	//节点下标为index的右孩子的下标
{
	return (index << 1) + 2;
}
static inline int PARENT_PQ(int index)	//节点下标为index的父节点的下标
{
	return (index - 1) / 2;
}
/* 保持堆的性质,此函数实现将某个子树的根节点按照堆的性质下降到某个子孙节点 */
static void HEAPIFY_PQ(PQ *desc, int index)	
{
	int left = LEFT_PQ(index);
	int right = RIGHT_PQ(index);
	int largest;
	PQ_element *tmp = NULL;

	for (; left < desc->heap_size || right < desc->heap_size; 
			left = LEFT_PQ(index), right = RIGHT_PQ(index)) {
		if (left < desc->heap_size && 
				desc->compar(desc->base[left]->data, desc->base[index]->data) > 0) 
			largest = left;
		else largest = index;
		if (right < desc->heap_size && 
				desc->compar(desc->base[right]->data, desc->base[largest]->data) > 0)
			largest = right;
		if (largest == index)
			break;
		tmp = desc->base[index];
		tmp->index = largest;
		desc->base[largest]->index = index;
		desc->base[index] = desc->base[largest];
		desc->base[largest]= tmp;
		index = largest;
	}
}
/* 分配一个节点 */
PQ_element *malloc_PQ(size_t size)
{
	PQ_element *e = NULL;
	
	e = malloc(sizeof(PQ_element));
	if (e == NULL)
		goto end;
	e->data = malloc(size);
	if (e->data == NULL) {
		free(e);
		e = NULL;
		goto end;
	}
	e->index = -1;
end:
	return e;
}

void free_PQ(PQ_element *ptr)
{
	PQ_element *e = (PQ_element *)ptr;
	if (!e)
		return;
	if (!(e->data)) {
		free(e);
		return;
	}
	free(e->data);
	free(e);
}

PQ *create_PQ(int nmemb, compar_t compar, change_key_t change_key)
{
	PQ *ret = NULL;
	PQ_element *t = NULL;

	ret = (PQ *)malloc(sizeof(PQ));
	if (ret == NULL) {
		goto end;
	}
	ret->compar = compar;
	ret->change_key = change_key;
	ret->heap_size = 0;
	ret->len = nmemb;
	t = malloc(sizeof(PQ_element *) * nmemb);
	if (t == NULL) {
		free(ret);
		ret = NULL;
		goto end;
	}
	memset(t, 0, sizeof(PQ_element *) * nmemb);
	ret->base = (PQ_element **)t;
end:
	return ret;
}

void destroy_PQ(PQ *desc)
{
	if (!desc)
		return;
	if (desc->base)
		free(desc->base);
	free(desc);
}

int insert_PQ(PQ *desc, PQ_element *x)
{
	PQ_element *tmp = NULL;
	int ret = -1, i;

	if (desc->heap_size >= desc->len) {
		tmp = realloc(desc->base, sizeof(PQ_element *) * (desc->len + 5));
		if (tmp == NULL) {
			goto end;
		}
		memset(&tmp[desc->len], 0, sizeof(PQ_element *) * 5);
		desc->base = (PQ_element **)tmp;
		desc->len += 5;
	}
	x->index = desc->heap_size;
	desc->base[desc->heap_size] = x;
	desc->heap_size++;
	i = x->index;
	while (i > 0 && desc->compar(desc->base[PARENT_PQ(i)]->data, desc->base[i]->data) < 0) {
		tmp = desc->base[i];
		tmp->index = PARENT_PQ(i);
		desc->base[PARENT_PQ(i)]->index = i;
		desc->base[i] = desc->base[PARENT_PQ(i)];
		desc->base[PARENT_PQ(i)] = tmp;
		i = PARENT_PQ(i);
	}
	ret = 0;
end:
	return ret;
}

int delete_PQ(PQ *desc, const PQ_element *x)
{
	int i = x->index;

	desc->base[i] = desc->base[desc->heap_size - 1];
	desc->base[desc->heap_size - 1] = NULL;
	desc->base[i]->index = i;
	desc->heap_size--;
	HEAPIFY_PQ(desc, i);
	return 0;
}

PQ_element *root_PQ(PQ *desc)
{
	if (desc && desc->base)
		return desc->base[0];
	return NULL;
}

PQ_element *extract_PQ(PQ *desc)
{
	if (!desc || !(desc->base))
		return NULL;
	if (desc->heap_size <= 0)
		return NULL;
	PQ_element *max = desc->base[0];
	desc->base[0] = desc->base[desc->heap_size - 1];
	desc->base[desc->heap_size - 1] = NULL;
	if (desc->base[0])
		desc->base[0]->index = 0;
	desc->heap_size--;
	HEAPIFY_PQ(desc, 0);
	return max;
}

void change_key_PQ(PQ *desc, PQ_element *x, const void *key)
{
	int i = x->index;
	PQ_element *tmp = NULL;

	desc->change_key(x->data, key);
	while (i > 0 && desc->compar(desc->base[PARENT_PQ(i)]->data, desc->base[i]->data) < 0) {
		tmp = desc->base[i];
		tmp->index = PARENT_PQ(i);
		desc->base[PARENT_PQ(i)]->index = i;
		desc->base[i] = desc->base[PARENT_PQ(i)];
		desc->base[PARENT_PQ(i)] = tmp;
		i = PARENT_PQ(i);
	}
}
/******************************/
